package com.qch.edu.lagou.algorithm.half;

/**
 *
 * 存在问题：当出现次数1在边缘会超出边界->已修改
 *
 *
 * @Author qch
 * @Date 2021/7/14
 * 一个有序数组有一个数出现1次，其他数出现2次，找出出现一次的数
 * 比如：1 1 2 2 3 3 4 4 5 5 6 6 7 出现1次的数是7
 * 暴力：
 * O(n)
 * hash：
 * O(n)
 * 关键：时间复杂度 O(logn)-》二分
 * 思路：
 * 使用二分查找： 1 有序、 2、时间复杂度 O(logn)
 * 偶数位索引跟后面的比相同，奇数位索引跟前面的比相同 则说明前面的都对
 * 偶数位索引跟前面的比相同，奇数位索引跟后面的比相同 则说明后面的都对
 * <p>
 * 同理：超级水王：找出数组里出现次数最多的数——》方案：一次删掉两个不同的数，水王数会被剩下来
 */
public class FindJustOne {
    //老师的
    public static int binarySearch(int[] nums) {
        //低位索引
        int low = 0;
        //高位索引
        int high = nums.length - 1;
        //中间索引
        int mid = 0;
        while (low <= high) {
            mid = (low + high) / 2;
            //偶数位
            if (mid % 2 == 0) {
                // 与后面的数相等
                if (nums[mid] == nums[mid + 1]) { //前面的都对
                    low = mid + 1;
                }

                // 与前面的数相等
                else if (nums[mid] == nums[mid - 1]) {
                    //后面的都对
                    high = mid - 1;
                }
                // 就是这个数
                else {
                    return nums[mid];
                }
            }
            //奇数位
            else {
                // 与前面的数相等
                if (nums[mid] == nums[mid - 1]) { //前面的都对
                    low = mid + 1;
                }
                //与后面的数相等
                else if (nums[mid] == nums[mid + 1]) {
                    //后面的都对
                    high = mid - 1;
                }
                // 就是这个数
                else {
                    return nums[mid];
                }
            }
        }
        // low=high
        return nums[low];
    }

    public static int binarySerch(int[] nums) {
        int low = 0;
        int high = nums.length - 1;
        int mid;
        while (low <= high) {
            mid = (low + high) / 2;
            //对临界值的判断
            if(mid + 1>nums.length - 1)
            {
                return nums[mid];
            }
            if(mid - 1<0)
            {
                return nums[mid];
            }
            if (mid % 2 == 0) {
                //偶数位和后面的比，如果相同，说明前面的都对，向后折半查
                if (nums[mid] == nums[mid + 1]) {
                    low = mid + 1;
                } else if (nums[mid] == nums[mid - 1])//和前面的比相同，说明后面的都对，向前折半查
                {
                    high = mid - 1;
                } else {
                    //既不等于前，也不等于后
                    return nums[mid];
                }
            } else {
                //奇数位和后面的比，如果相同，说明后面的都对，向前折半查
                if (nums[mid] == nums[mid + 1]) {
                    high = mid - 1;
                } else if (nums[mid] == nums[mid - 1])//和前面的比相同，说明后面的都对，向前折半查
                {
                    low = mid + 1;
                } else {
                    //既不等于前，也不等于后
                    return nums[mid];
                }
            }
        }
        return nums[low];
    }

    public static void main(String[] args) {
        int[] nums = {1,1,2,2,3,3,4,4,5,5,6,6,7};
        System.out.println(binarySerch(nums));
    }
}
